package findknum;

/**
 * 类快速排序
 */
public class FindKNumOfQuickSort1 {


    /**
     * @param array 要遍历的数组
     * @param low   二分法的起始
     * @param high  二分法的终止位置
     * @param k     查找的第k小的元素
     * @return
     */
    public static int findK(int[] array, int low, int high, int k) {
        //中间位置
        int i = low;
        int j = high;
        int mindNum = array[low];
        //双指针开始遍历
        while (i < j) {
            //逆向遍历。找到小于mindNum的元素
            while (i < j && mindNum <= array[j]) {
                j--;
            }
            if (i < j) {
                array[i] = array[j];
                i++;
            }
            //正向遍历。找到大于mindNum的元素
            while (i < j && mindNum >= array[i]) {
                i++;
            }
            if (i < j) {
                array[j] = array[i];
                j--;
            }
        }
        array[i] = mindNum;
        //如果k正好等于i
//        if((i-low)==k){
        if ((k - 1) == i - low) {
            return mindNum;
//        }else if((i-low)<k){
        } else if ((k - 1) < i - low) {
//            return findK(array,low,i-low,k);
            return findK(array, low, i - 1, k);
        } else {
//            return findK(array,i,high,(k-i)-1);
            return findK(array, i + 1, high, (k - 1) - (i - low));
        }
    }

    public static void main(String[] args) {
        int[] array = {89, 2, 4, 8, 9, 32, 11, 3, 21};

        System.out.println(findK(array, 0, array.length - 1, 1));
        System.out.println(findK(array, 0, array.length - 1, 2));
    }
}
